package com.lsa.letcode.the50.pow;

public class Solution {
	public double myPow(double x, int n) {
    	if (n == 0) {
    		return 1;
    	}
    	else if (x == 0) {
    		if (n > 0) {
    			return 0;
    		}
    		else {
    			return Double.POSITIVE_INFINITY;
    		}
    	}
    	boolean isNegativePow = n < 0;
    	
    	long nLong = n;
    	if (isNegativePow) { // make it positive
    		nLong = -nLong;
    	}

    	double res = myPowPositive(x, nLong);
        return isNegativePow? 1 / res : res;
    }
	
	/**
	 * Deals only with positive n powers
	 * @param x
	 * @param n
	 * @return
	 */
	private static double myPowPositive(double x, long n) {
		if (n == 0) {
    		return 1;
    	}
		double res = x;
    	{
    		long i = 1; // long to avoid overflow
    		for (; i + i < n; i += i) {
    			res *= res;
    		}
    		
    		res = res * myPowPositive(x, n - i);
    	}
    	return res;
	}
	
	public double myPow2(double x, int n) {
		return myPower(x, n);
	}
	
	public double myPower(double x, int n) {
		if (n == 0) {
			return 1;
		}
		else if (x == 0) {
			if (n < 0) {
				return Double.POSITIVE_INFINITY;
			}
			else {
				return 0;
			}
		}
		else if (n < 0) {
			return 1 / myPower(x, -n);
		}
		else {
			return power(x, n);
		}
	}
	
    private double power(double x, int n) {
    	if (n == 0) {
    		return 1;
    	}
    	double p = power(x, n / 2) * power(x, n / 2); 
		return n % 2 == 0? p : p * x;
	}
}